package co.za.alicrity.exactcover;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;

import co.za.alicrity.exactcover.linkedlist.Iterator;

public class TreeNodes {
	
  private List<TreeNodes> childNode = new ArrayList<TreeNodes>();
  private TreeNodes parentNode;
  
  private Integer solutionRow;
  private List<ColumnHeader> header = new ArrayList<ColumnHeader>();
  private List<Node> removedRow = new ArrayList<Node>();
  
  private ExactCoverSparceMatrix matrix;
  
  private SolutionList solutions;
  
  
  
  
  public TreeNodes(ExactCoverSparceMatrix matrix, TreeNodes parent, int rowNumber, SolutionList solutions){
	  this.matrix=matrix;
	  this.parentNode=parent;
	  this.solutions=solutions;
	  
	  if (rowNumber==-1){
		  ColumnHeader least = matrix.getColumnWithLeastAmount();
		  
		  int[] rowList = new int[least.getSize()];
		  int r=0;
		  Iterator<Node> i = least.getIterator();
		  while(i.hasNext()){
			  rowList[r++]=i.getNext().getRow();
		  }
		  
		  for (r=0;r<rowList.length;r++){
			  childNode.add(new TreeNodes(matrix, this, rowList[r], solutions));
		  }
		  
	  } else {
		  
		  solutionRow=rowNumber;
		  
		  Iterator<ColumnHeader> i = matrix.getIterator();
		  List<ColumnHeader> columnsWitNode = new ArrayList<ColumnHeader>();
		  while(i.hasNext()){
			  ColumnHeader cur = i.getNext();
			  if (cur.nodeExistsForRow(rowNumber)){
				  columnsWitNode.add(cur);
			  }
		  }
		  
		  HashMap<Integer, Integer> rowsToRemove = new HashMap<Integer, Integer>();
		  for (ColumnHeader cur : columnsWitNode){
			  Iterator<Node> nodeI = cur.getIterator();
			  while(nodeI.hasNext()){
				  int row = nodeI.getNext().getRow();
				  rowsToRemove.put(row, row);
			  }
		  }
		  
		  for (int row : rowsToRemove.keySet()){
			  i = matrix.getIterator();
			  columnheader:
			  while(i.hasNext()){
				  ColumnHeader cur = i.getNext();
				  if (cur.nodeExistsForRow(row)){
					  Node rem = cur.getNodeAtRow(row);
					  removedRow.add(rem.remove());
					  while(rem.getNextColumn()!=null){
						  rem=rem.getNextColumn();
						  removedRow.add(rem.remove());
					  }
					  continue columnheader;
				  }
			  }
		  }
		  
		  for (ColumnHeader cur : columnsWitNode){
			  header.add(matrix.remove(cur));
		  }
		  
		  
		  //Create child nodes
		  if (!matrix.isEmpty()){
			  ColumnHeader least = matrix.getColumnWithLeastAmount();
			  if (least.getSize()!=0){
			  
				  int[] rowList = new int[least.getSize()];
				  int r=0;
				  Iterator<Node> In = least.getIterator();
				  while(In.hasNext()){
					  rowList[r++]=In.getNext().getRow();
				  }
				  
				  for (r=0;r<rowList.length;r++){
					  childNode.add(new TreeNodes(matrix, this, rowList[r], solutions));
				  }
			  }
		  } else {
			  List<Integer> solutionsRows = new ArrayList<Integer>();
			  addSolutionToListAndCascadeUp(solutionsRows);
			  solutions.addSolution(solutionsRows);
		  }
		  
		  
		  
		  
		  
		  //Put everything back
		  Collections.reverse(header);
		  for (ColumnHeader cur : header){
			  matrix.putBack(cur);
		  }
		  
		  Collections.reverse(removedRow);
		  for (Node cur : removedRow){
			  cur.putBack();
		  }
		  
		  
		  
	  }
  }
  
  public void addSolutionToListAndCascadeUp(List<Integer> list){
	  if (solutionRow!=null)
		  list.add(solutionRow);
	  if (parentNode!=null){
		  parentNode.addSolutionToListAndCascadeUp(list);
	  }
  }
  
  public TreeNodes(ExactCoverSparceMatrix matrix, SolutionList solutions){
	  this(matrix,null,-1,solutions);
  }
  
  public String toString(){
	  return matrix.toString();
  }
 

}
